#include <stdio.h>
#include <stdlib.h>
// 2<=n<=30, arr[i] < 100000

int cnt_of1(int x) {
	int count = 0;
	while (x) {
		x &= (x-1);
		count++;
	}
	return count;
}

// 若干元素之和为tagert，限制：bitmap最多32位
int cal_nums(int arr[], int len, int target) {
	int N = 1<<len; 
	// 将选中情况转换为bitmap，对应位 置1表示选中该位置上的元素
	//例如len为4时, 0001 ~ 1111（0~15），总共有2^N种情况
	for (int bitmap = 1; bitmap < N; bitmap++)	 {	
		// if (cnt_of1(bitmap) == 3) {	//可以用来限定个数
			int sum = 0;
			for (int j = 0; j < len; j++) {	//遍历整个数组
				//位图中第j位被选中(从右到左)
				if (bitmap & (1 << j))	
					sum += arr[len-1 - j];
			}
			if (sum == target) {	
				return bitmap;	
			} else {
				sum = 0;	
			}
		// }
	}
	return -1;
}

int main()
{
	int arr[5] = {100, 50, 50, 110, 120}, n = 5, target = 210;
	printf("bitmap:%d\n",cal_nums(arr, n, target)); // 选中011（从右往左） = bitmap 3
	return 0;
}